#include <stdio.h>
#include <linkstack.h>

int isLeft(char c){
        int ret = 0;

        switch (c){
                case '<':
                case '(':
                case '[':
                case '{':
                case 39: // '单引号
                case 34: // "双引号
                        ret = 1;
                        break;
                default:
                        ret = 0;
                        break;
        }

        return ret;
}

int isRight(char c){
        int ret = 0;

        switch (c){
                case '>':
                case ')':
                case ']':
                case '}':
                case 39: // '单引号
                case 34: // "双引号
                        ret = 1;
                        break;
                default:
                        ret = 0;
                        break;
        }

        return ret;
}

int match(char left, char right){
        int ret = 0;

        switch (left){
                case '<':
                        ret = (right == '>');
                        break;
                case '(':
                        ret = (right == ')');
                        break;
                case '[':
                        ret = (right == ']');
                        break;
                case '{':
                        ret = (right == '}');
                        break;
                case 39: // '单引号
                        ret = (right == 39);
                        break;
                case 34: // "双引号
                        ret = (right == 34);
                        break;
                default:
                        ret = 0;
                        break;
        }

        return ret;
}

int scanner(const char* code){
        int ret = 0;
        int i = 0;
        LinkStack* stack = NULL;

        stack = LinkStack_Create();

        while (code[i] != '\0'){
                if( isLeft(code[i]) ){ //如果是左符号压入栈中
                        LinkStack_Push(stack, (void *)(code+i)); //&code[i]
                }

                if ( isRight(code[i]) ){ //如果是右符号弹栈
                        char* ch = (char*)LinkStack_Pop(stack);

                        if((ch == NULL) || (!match(*ch, code[i]))){
                                printf("%c does not match\n", code[i]);
                                ret = 0;
                                break;
                        }       
                }

                i++;
        }

        if(LinkStack_Size(stack) == 0 && code[i] == '\0'){
                printf("Success!\n");
                ret = 1;
        }else{  
                printf("Invalid code!\n");
                ret = 0;
        }

        return ret;
}

///////////////////////////////////
int isNumber(char c){
        return ('0' <= c) && (c <= 9);
}

int isOperator(char c){
        return (c == '+') || (c == '-') || (c == '*') || (c == '/');
}

void output(char c){
        if( c != '\0' ){
                printf("%c", c);
        }
}

int isLeft2(char c){
       return (c == '('); 
}

int isRight2(char c){
        return (c == ')');
}

int priority(char c){
        int ret = 0;

        if( (c == '+') || (c == '-') ){
                ret = 1;
        }

        if( (c == '*') || (c == '/') ){
                ret = 2;
        }

        return ret;
}

void transform(const char* exp){
        int i = 0;
        LinkStack* stack = NULL;

        stack = LinkStack_Create();

        while ( exp[i] != '\0' ){
                if( isNumber(exp[i]) ){//如果是数字,直接输出
                        output(exp[i]);
                }else if( isOperator(exp[i]) ){
                        //如果是栈顶的优先级高,把栈顶元素弹出来,之后入栈
                        while ( priority(exp[i]) <= priority((char)(int)LinkStack_Top(stack)) ){
                                output((char)(int)LinkStack_Pop(stack));
                        }

                        LinkStack_Push(stack, (void*)(int)exp[i]);
                }else if( isLeft2(exp[i]) ){
                        LinkStack_Push(stack, (void*)(int)exp[i]);
                }else if( isRight2(exp[i]) ){
                        while ( !isLeft2((char)(int)LinkStack_Top(stack)) ){
                                output((char)(int)LinkStack_Pop(stack));
                        }

                        LinkStack_Pop(stack);
                }else{
                        printf("Invalid expression!");
                        break;
                }
                i++;
        }
        
        while (  LinkStack_Size(stack) > 0 && exp[i] == '\0' ){
                output((char)(int)LinkStack_Pop(stack));
        }

        LinkStack_Destory(stack);
}

int main(int argc, char const *argv[])
{
        //案例一 就近匹配 遇到左符号压栈 遇到右符号出栈 判断最终栈是否为空 为空就是正确的
        //编译器如何检查源代码的
        //const char* code = "#include <stdio.h> int main() { int a[4][4]; int (*p)[4]; p=a[0]; return 0; }";
        //scanner(code);

        //案例二
        // 5 + 4 中缀表达式 运算符在中间
        // 5 4 + 后缀表达式 运算符在末尾
        //如何将中缀转后缀？
                //对于数字直接输出
                //对于符号: 
                        //左括号: 进栈  
                        //运算符号: 与栈顶符号进行优先级比较
                                //若栈顶符号优先级低；此符号进栈(默认栈顶若是左括号,左括号优先级最低)
                                //若栈顶符号优先级不低；将栈顶符号弹出输出,之后进栈
                        //右括号: 将栈顶符号弹出并输出,直到匹配左括号
                //遍历结束: 将栈中的所有符号弹出并输出
        transform("8+(3-1)*5");

        return 0;
}
